• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:

    公开号:WO1991017507A1
    申请号:PCT/JP1991/000604
    申请日:1991-05-07
    公开日:1991-11-14
    发明作者:Takashi Kan
    申请人:Mitsubishi Denki Kabushiki Kaisha；
    IPC主号:G06F15-00
    专利说明:
    [0001] 明 細 書
    [0002] 並列データ処理システム
    [0003] 技術分野
    [0004] この発明は、 高速データ処理を行なうための並列データ処理分野 に関するものである。 背景技術
    [0005] 第 4図と第 5図は、 例えば文献 "Highly Parallel Computing " (G.S.Almasi, A . Gottlieb 著， The Ben ja mi n/Cu minings Publising Company, Inc. ,1989) PPlll-112,pp301-476に示される従来の並列デ ータ処理装置の例を示す基本構成図である。 第 4図は、 制御の流れ がーつで， 処理されるデータの流れが複数である S I M D (Single Instruction Stream, Multiple Data Streams) 型の並列データ処理 装置、 第 5図は、 制御の流れもデータの流れも複数である M I MD (Multiple Instruction Streams, Multiple Data Streams^型の並列 データ処理装置を示す。
    [0006] 第 4図中、 1， 2， 3及び 4は演算器、 5， 6 , 7及び 8は各々 の口一カルメモリ、 9はメモリバス、 1 0は共有メモリ、 1 1 は装 置全体の制御を行う全体制御部である。 また、 第 5図中、 2 1， 2 2， 2 3及ぴ 24は演算器、 2 5 , 2 6， 2 7及び 2 8は各々の 口一カルメモリ、 3 5， 3 6， 3 7及び 3 8は各々の制御部、 2 9 はメモリバス、 3 0は共有メモリ、 3 1は全体制御部である。
    [0007] 次に動作について説明する。
    [0008] 第 4図の S I MD型並列データ処理装置では、 プログラムが実行 される全体制御部 1 1 から全ての演算器 1〜4へ同一命令が同時に 発せられ、 各々の口一カルメモリ 5〜 8のデータ を処理する。 ま た、 処理の途中で必要に応じて、 メモリバス 9 を介して共有メモリ 1 0にアクセスする。
    [0009] 一方、 第 5図の M I M D型並列データ処理装置では、 各プロセッ ザの制御部 3 5〜 3 8で各々プログラムが実行され、 各々の演算器 2 1〜24に対して命令が発せられ、 次にこれにより、 各々のロー カルメモリ 2 5〜 2 8のデータに対して処理が行われる。 また、 処 理の途中で必要に応じて、 メモリバス 29 を介して共有メモリ 30 にアクセスする。 全体制御部 3 1は装置全体の同期や監視のための 制御を行う。
    [0010] このような従来の S I MD型と M I M D型の並列データ処理装置 には、 それぞれに長所と短所があった。 すなわち、 S I MD型並列 データ処理装置の場合は制御の流れが-一本であるため、 制御が単純 で， 大規模な並列処理を行うことが容易であり、 非常に高い高速性 が得られやすい。 しかし、 その反面， 処理に柔軟性が少なく、 複雑 な処理には適さない。
    [0011] 一方、 M I MD型並列データ処理装置の場合は各プロセッサが個 々に動作するため、 各々が高度な処理を行える。 しかし、 その分だ け制御は複雑になリ、 大規模な並列処理には適さない。
    [0012] このように、 S I MD型と M I MD型では並列処理の内容がかな リ異なるため、 各々に適した応用分野がある。 そのため、 どちらか 一方の方式で広い応用分野をカバ一することは非常に困難となる。
    [0013] 以下では、 並列データ処理の適用分野として特に重要な数値計算 と画像処理の分野を例にとり具体的に説明する。
    [0014] まず、 数値計算の分野においてその処理モデルは、 （ 1 ) モンテ カルロシミュレーショ ンに代表される粒子系モデル、 （ 2 ) 物理現 象を対象とした変微分方程式の解法を行なう連続系モデル、 （ 3 ) ネッ トワークの解析などを対象とした連立方程式の解法を行なう離 散系モデル、 に大きく分類できる。 これらのうち、 連続系モデルは 大量の規則的かつ局所的演算の繰り返しであるため、 S I MD型の 大規模な並列処理が適している。 一方、 離散系モデルでは大規模な 並列性は必要ないが複維な処理が要求されるため、 中規模の M I M D型の並列処理が適している。 さらに、 粒子系モデルの場合は大規 模かつ複雑な処理が要求される場合が多く、 条件やデータ数によ リ、 S I M Dと M I M Dの使い分けが必要である。
    [0015] 次に、 画像処理の場合は、 （ 1 ) 濃度値変換や 2値化のような 画素単位の処理、 （ 2 ) 空間フィルタの様な近傍画素間の処理、 ( 3 ) 幾何変換や高速フーリエ変換の様な大局的な処理、 （4 ) ラ ベリングゃ境界線検出の様な浸透または追跡型の処理、 に大きく分 類される。 これらのうち、 画素単位処理や近傍画素間処理には単純 で大規模な処理であるため S I M Dが適しており、 大局処理では複 雑で広範な処理が必要なため M I M D型が適している。 浸透/追跡 型は条件やデータ数により、 S I M Dと M I M Dの使い分けが必要 である。
    [0016] このように、 数値計算と画像処理の例をみても、 ある特定の分野 でさえ様々なタイプの処理があリ、 一つの並列処理アーキテクチャ だけで最適な並列処理を施すことは困難である。
    [0017] この発明は上記のような問題点を解消するためになされたもの で、 S I M D型と M I M D型の両者の長所を生かし、 かつ各々の欠 点をカバーし、 広い応用分野のどの分野でも最適に近い並列処理 アーキテクチャ を適用可能とすることを目的と している。 発明の開示
    [0018] この発明に係る並列データ処理システムは、 制御の流れが一つ で， 処理されるデータの流れが複数である第 1の並列データ処理装 置， すなわち S I M D型の並列データ処理装置と、 制御の流れも データの流れも複数である第 2の並列データ処理装置， すなわち M I M D型の並列データ処理装置とを共有のバスとメモリで接続する とともに、 各々の並列データ処理装置に適した処理を行わせるシス テム制御部を備えることにより、 広い範囲で最適な並列処理方式を 適用できるようにしたものであり、 対象となる処理が単純で大量の データ処理が必要なものを S I M D型並列データ処理装置で処理 し、 複雑な処理で少量のデータ処理の場合は M I MD型並列データ 処理装置で処理する。 また、 一つのプログラムをモジュールに分 け、 モジュール毎に割り振ることも可能で、 これにより各々の適し た処理を並列に， もしくはパイプライン的に行うことができる。 こ れらのデータの受け渡しは共有メモリを介して行われる。 すなわ ち、 どちらか一方の型の並列データ処理装置を拡充するよりは、 こ のように両者の型を結合し、 補完し合った方が機能的にもコスト的 にも有効である。
    [0019] また、 本発明では、 上記のような数値計算や画像処理の分野での 問題を解決するため、 S I MD型と M I MD型の異なる二つのタイ プの並列データ処理装置を共有メモリ と高速多重バスによリ密結合 し、 相補的に使用することによ り、 広い分野で効率的な並列処理を 施すことができるハイプリ ッ ド型並列データ処理システムを実現す る。
    [0020] このようなハイブリッ ドの考えを取り入れた並列アーキテクチャ と して、 従来の S I M Dを M I M D的に機能拡張した M S I MD (Multiple SIMD)を採用した University of Texas の T RA C Iexas Reconf igurable Array Computer) や Purdue University の P A S M (Partitionable SIHD/HIHD system)などがあった。 し力、 し、 これらのアプローチと比べ本発明では、 次にような特徴があ る。 （ 1 ) 同等規模の S I MDと M I MDの二つの並列データ処理 装置を個別に持ち対等に密結合したこと、 （ 2 ) 雨並列データ処理 装置が各々 S I MDと M I MDの長所を生かしつつ従来の欠点を補 う機能拡張を行なっていること、 （ 3 ) 雨並列データ処理装置間の データ転送を効率的に行なうため高速多重バスと大容量高速共有メ モリを持つこと、 （4 ) 従来の並列処理では実現できなかったハイ ブリ ジ ドなパイプライン処理や並列処理が可能である。
    [0021] このようなハイブリツ ド型並列データ処理システムを、 画像処理 のような大規模でかつ複維な処理に適用することによリ、 従来のシ ステムでは有効時間内での処理が困難た'つた処理を実用時間内で高 速に処理することができる。 図面の簡単な説明
    [0022] 第 1図は本発明の一実施例による並列データ処理システムを示す システム構成図、 第 2図は本発明を適用したシステム例を示す具体 的構成図、 第 3図は本発明の実施によ リ実現できる並列処理の流れ を示す図である。 第 4図は従来の S I M D型並列データ処理装置の 例を示す基本構成図、 第 5図は従来の M I M D型並列データ処理装 置の例を示す基本構成図である。 発明を実施するための最良の形態
    [0023] 以下、 この発明の一実施例を図について説明する。
    [0024] 第 1図は実施例のシステム構成図であり、 図において、 5 0は前 記第 4図と同様の S I M D型の並列データ処理装置、 5 1は前記第 5図と同様の M I M D型の並列データ処理装置である。 また、 4 1 はこの両者で共有するメモリバス、 4 2は同じく共通に利用し、 両 者のデータの受け渡しを行う共有メモリ、 4 3は応用プログラムの 中で、 各処理を各々によリ適した方の並列データ処理装置へ振り分 けるためのシステム制御部である。
    [0025] 次に動作について説明する。
    [0026] 第 1図のシステムにおいて、 応用プログラムの実行制御はシステ ム制御部 4 3で行われる。 プログラムの中で、 S I M D型向きの処 理， すなわち処理は単鈍であるが大量のデータ処理を必要とするも のは S I M D型並列データ処理装置 5 0 へ、 また、 M I M D型向き の処理， すなわち複雑な処理で少量のデータ処理のものは M I M D 型並列データ処理装置 5 1へ振り分けられる。 この場合、 ユーザか らは両者を明示することもできるし、 暗示的に使用することもでき る。 暗示的な例はライブラリであり、 ユーザがある機能のライブラ リを使用した場合には、 そのライブラリをコールした時点で最適な 方の並列データ処理装置が指示される。
    [0027] 一つのプログラム内で S I MD型並列データ処理装置 5 0と M l MD型並列データ処理装置 5 1 を両方使用する大きなレベルでの並 列処理やパイプライン処理も可能である。 この時には、 システム制 御部 4 3の制御で行われるが、 データの受け渡しはメモリバス 4 1 を介し共有メモリ 4 2により行われる。 このため、 メモリバス 4 1 は高速なものが要求される。
    [0028] なお、 上記実施例では、 各々の並列データ処理装置が 4台のプロ セッサから成る例を示したが、 通常、 S I M D型の場合は非常に多 数のプロセッサを持ち、 M I MD型の方は比較的少数である。 これ らのプロセッサ台数の比率は、 各々のプロセッサの性能や応用プロ グラムの性格によつて決定されるものである。
    [0029] また、 前述の雨並列データ処理装置を使った大きなレベルでの並 列動作やパイプライン処理を行う場合、 バス 4 1 を一時的に分雛し たり、 バスを 2本以上持たせることも有効となる。
    [0030] 以上のように、 この発明によれば、 S I M D型と M I M D型の並 列データ処理装置を結合し、 各並列データ処理装置に適した処理を 行わせるようにしたので、 S I MD型か M I MD型のどちらか一方 だけを拡充して使用し広い応用分野に適用するよリも、 性能とコス 卜の両面で有利となり、 輻広い分野でよリ適した並列処理を行うこ とができるようになる効果がある。
    [0031] 次に、 本発明を実現した具体的な適用例を第 2図に示す。 基本構 成は第 1図と同様であるが、 個々のブロックの中身をさらに細かに 示している。
    [0032] 第 2図中、 4 1 , 4 2 , 4 3， 5 0， 5 1のブロックはそれぞれ 第 1 図と同様、 共有メモ リバス， 共有メモリ， システム制御部， S I MD型並列データ処理装置， M I M D型並列データ処理装置を 示す。 共有メモリバス 4 1は、 2本のバス 9 6 , 9 7 と各々のバス接続 部 9 4， 9 5で構成される。 このような多重バスと したのは、 二つ の並列データ処理装置 5 0 , 5 1 からの共有メモリ 4 2へのァクセ ス競合を避けるためと、 システム制御部 4 3からのデータの入出力 と演算を同時に行なうためである。 通常のモードでは、 バスに接続 されている全ての信号は、 どちらか空いている方のバスを使用でき るほか、 どちらかの並列データ処理装置が同時に両方のバスを占有 して、 入力と出力にそれぞれ使用することもできる。 また、 これら の二つのバス 9 6， 9 7はバス接続部 9 4， 9 5で接続される。 こ のバス接続部 9 4， 9 5はバス 9 6， 9 7を S I M D型並列データ 処理装置 5 0側と M I M D型並列データ処理装置 5 1側に分離した り、 接続したりする機能を持つ。 この切り替え機構は、 セレクタに より実現され、 接続時はそのままつながり、 切り離し時はバス接続 部 9 4， 9 5の両側にあるバス終端抵抗へ接続され、 二つの並列 データ処理装置 5 0 , 5 1のそれぞれ独立したバスと して使用でき る。 このバス接続部 9 4， 9 5は、 システム制御部 4 3からの信号 により接続と切リ離しの制御が行なわれる。
    [0033] 共有メモ リ 4 2は、 一般に複数のセグメン トに分割されるが第 2図では 4つのセグメン トの例を示す。 各々のセグメント 9 8， 9 9 , 1 0 0， 1 0 1は 1 6メガバイ 卜の容量を持ち、 個別に共有 メモリバス 4 1 に接続されている。 共有メモリ 4 2を使用する場合 はセグメント番号とセグメント内アドレスを指定する。 通常のユー ザプログラムは， 論理セグメン ト番号を使用し、 物理セグメン ト番 号との対応はシステム制御部 4 3によリ行なわれる。 また、 各セグ メン トそれぞれが独自にアドレス計算を行なう機能を持ち、 余分な アドレス情報がバスを使用することを避けることによ り、 二つの並 列データ処理装置 5 0， 5 1は共有メモリ 4 2と高速なデータ転送 を行なうことができ、 本発明の効果をさらに向上することができる (特願昭 61- 288740 号） 。 システム制御部 4 3は、 データ処理部 9 0， メモリ部 9 1 ， バス 接続部 9 2， ディスク装置 9 3， 内部バス 1 0 6から構成される。 通常、 ユーザプログラムはデータ処理部 9 0で処理され、 プログラ ムはメモリ部 9 1に格鈉されている。 処理されるデータはディスク 装置 9 3に格鈉されておリ、 共有メモリバス接続部 9 2を経由して 共有メモリ 4 2に転送され、 いずれか又は面方の並列データ処理装 置 5 0 , 5 1により処理される。 また、 処理されたデータはバス接 続部 9 2を経由してディスク装置 9 3に格納される。
    [0034] S I MD型並列データ処理装置 5 0は、 全体制御部 1 1， 出力制 御部 1 0 2， 入力制御部 1 0 3， 4 0 9 6個の演算要素 1 0 8から 構成される。 一つの演算要素 1 0 8は 8ビッ ト演算器 1 と 1 6 K ビッ 卜の口一カルメモリ 5から構成され、 これらが格子状に 4近傍 演算要素間で接続されてる。 各演算器は 8ビッ トの加減算器のほか 複数の制御フラグ， 1 2 8ビッ 卜のレジスタファイルなどから構成 される （US Patent No.4, 858, 110) 。 S I MD型並列データ処理装 置 5 0全体の制御は全体制御部 1 1 によって行なわれ、 ここから同 一の命令が全ての演算要素 1 0 8に同時に送られる。 処理される データは、 全体制御部 1 1の指令により、 共有メモリ 4 2から入力 制御部 1 0 3を経由して各演算要素 1 0 8に送られる。 また、 処理 されたデータは出力制御部 1 0 2を経由して共有メモリ 4 2に返さ れる。 データの入出力と演算をオーバ一ラップさせることも可能 で、 それによりデータのブロック単位にパイプライン的に処理を高 速化することができ、 本発明をさ らに効果的にすることができる (特願昭 59-29485号， 特公平 1-26108 号公報） 。 これらの機能によ リ、 S I MD型の並列処理を実現し、 大規模なデータを同時に並列 処理することができる。
    [0035] M I MD型並列データ処理装置 5 1は、 全体制御部 3 1， 入出力 制御部 1 04 , 1 0 5， 8つの演算要素 1 0 9及びこれらを接続す るバス 1 0 7から構成される。 各演算要素 1 0 9は、 3 2ビッ ト演 算器 2 1， 1 MBの口一カルメモリ 2 5， 制御部 3 5を持ち、 それ ぞれ個別に異なる命令列を実行することができる。 M I M D型並列 データ処理装置 5 1全体の制御は全体制御部 3 1 によって行なわ れ、 ここから各演算要素 1 0 9に実行される命令列が送られ、 制御 される。 また、 処理されるデータは全体制御部 3 1の指令により、 共有メモリ 4 2から入出力制御部 1 04， 1 0 5のいずれかを経由 して各演算要素 1 0 9に送られる。 また、 処理されたデータは入出 力制御部 1 04， 1 0 5のいずれかを経由して共有メモリ 4 2に返 される。
    [0036] 次に、 本発明の実施によリ実現できる 4つの並列処理について第 3図を用いて説明する。 第 3図は、 第 2図で示したシステム構成例 によ り、 各並列処理の流れを時間に沿って記述したもので、 基本 的に二つの並列データ処理装置 5 0， 5 1による二つの並列処理 の流れが存在する。 6 0は S I M D型並列データ処理装置 5 0の 4 0 9 6個の演算要素 1 0 8が作リ出す多数の微細な S I MD型並 列処理の流れを示し、 6 6 , 6 8 , 7 2は S I MD型並列デ一タ処 理装置 5 0により演算が行なわれている部分を示す。 6 1は M I M D型並列データ処理装置 5 1の 8つの演算要素 1 0 9が作り出す高 機能で融通性が高い M I MD型並列処理の流れを示し、 6 5 , 7 0， 7 3は M I M D型並列データ処理装置 5 1により演算が行なわれて いる部分を示す。 6 2は共有メモリ内のデータを示し、 6 3 , 64， 6 7， 6 9， 7 1， 74 , 7 5がそれぞれアクセスされるデータを 示す。 1 1 0 , 1 1 1 , 1 1 2はそれぞれ S I MD型並列デ一タ処 理装置 5 0と M I M D型並列データ処理装置 5 1によるハイブリツ ド処理の流れを示す。
    [0037] 個々の並列処理 6 0， 6 1は従来からあり、 これまでこのどちら かの並列処理を使用していたが、 本発明の実施によ り、 さらにこれ らを組み合わせたハイブリ ッ ド並列処理特有の新たな並列処理の流 れを生み出すことができる。 即ち、 本実施例では、 従来の方式では 実現できなかった次の 3種類の並列処理を使用できる。
    [0038] ( 1 ) システム制御部 4 3で実行される一つ又は複数のプログラ ムによ り、 S I M D型並列データ処理装置 5 0と M I M D型並列 データ処理装置 5 1 をそれぞれ独立に同時に使用し、 共有メモリ内 の異なるデータ 64， 6 3に対して処理を施すことができる。 この ようなハイブリツ ド並列処理を 1 1 0で示す。 この機能によリ、 一 つのシステムにおいて、 同一の手続きで異なるタイプの並列処理を 同時に使用できる。 従来の方式では、 異なるタイプの並列処理手法 を利用するためには異なるシステムを使用しなくてはならず、 手続 きも異なっていた。
    [0039] ( 2 ) 連続する一連のデータセッ 卜 （例えば画像） 単位に二つの 並列データ処理装置 5 0， 5 1 をパイプライン的に処理させるハイ プリッ ド並列処理を 1 1 1に示す。 共有メモリのデータ 6 7を使用 し、 まず S I MD型並列データ処理装置 5 0が処理 6 8を施し、 そ の結果を共有メモリ （データ 6 9 ) 経由で M I M D型並列データ処 理装置 5 1 に渡し、 継続して異なる並列処理 7 0を施す。 この処理 を行なうためには、 システム制御部 4 3が同期制御やデータセッ 卜 の制御を行なう。 二つの並列データ処理装置 5 0 , 5 1間のデータ の受け渡しは共有メモリ 4 2を通して行なわれ、 このオーバ一へッ ドを最小に抑えるため、 共有メモ リバス 9 6， 9 7と共有メモリ 4 2の各セグメン ト 9 8， 9 9， 1 0 0， 1 0 1は各々の並列デ一 タ処理装置 5 0， 5 1に独立に使用される。 これらの結果、 対象の 処理を機能レベルに細かに分割し、 各機能によリ適した並列データ 処理装置を用い、 データセッ 卜単位で無駄のないパイプライン処理 を行なうことができる。
    [0040] ( 3 ) 二つの並列データ処理装置 5 0 , 5 ] を個別に独立に平行 動作させるハイプリッ ド並列処理を 1 1 2に示す。 この場合は共有 メモリのデータ 7 1 を使用し、 S I M D型並列データ処理装置 5 0 が処理 7 2を施し、 同時に M I MD型並列データ処理装置 5 1が同 じデータ 7 1 を使用して異なる並列処理 7 3を施す。 この場合、 異 なるプログラムが各々の並列データ処理装置 5 0 , 5 1で個別に動 作することもあれば、 同一プログラム内で同一データセッ トに対し て異なる並列アルゴリズムを用いて並列処理を行なうこともある。 このような並列処理は、 アルゴリズム， 収束性， 精度， 並列度など が異なる並列処理方式を同時に同一データに施せるため、 両者の結 果を比較して信頼性を上げたり、 早く結果が出た方を使用して性能 を上げたりすることができる。 この様な処理は従来の方式では実現 できずハイブリツ ド手法特有のものである。
    [0041] 以上のように、 本発明の実施により、 ハイブリッ ド型並列処理特 有の新しい並列処理を実現することができ、 空間的にも時間的にも 従来方式以上に並列処理の適用範囲を広めることができる。
    [0042] 次に、 本発明を実施するためのソフ トウェア構成例を示す。 本発 明では、 ュ一ザが使用するための並列処理ライブラリと、 二つの並 列データ処理装置 5 0 , 5 1や共有メモリ 4 2を使いハイブリッ ド 処理を制御するためのシステム制御ソフ トウェァがある。
    [0043] まず、 並列処理ライブラリは、 ユーザに二つの並列データ処理装 置 5 0， 5 1 を容易に使用できるように提供されるもので、 通常、 適した方の並列データ処理装置用に用意され登録されている。 ま た、 同一の処理でありながら、 それぞれの並列データ処理装置用に 異なるアルゴリズムで別々に用意されているものもある。 ュ一ザは 通常、 システム制御部 4 3の上で動作するュ一ザプログラムからサ ブル一チンコールによリ、 これらのライブラリを使って二つの並列 データ処理装置 5 0， 5 1 を使用する。 いずれの並列データ処理装 置を使用するかは、 ライブラ リ を指定した時点でシステム制御部 4 3が認識して、 適した方の並列データ処理装置に起動をかけるが、 予め明示することもできる。 このほか、 ユーザが直接いずれかの並 列データ処理装置の実行ライブラリを記述することもできる。 また、 かなり制約はあるものの、 ュ一ザプログラムを、 自動的にいずれか 適した方の並列データ処理装置を選んで並列ライブラリに置き換え るコンパイラも有効である。
    [0044] 一方、 システム制御ソフ トウェアは、 本発明のハイブリッ ド並列 処理を実現するための制御ソフ トウヱァでは、 （i ) 二つの並列 データ処理装置 5 0 , 5 1の並列及びパイプライン制御、 （ii ) 各 並列データ処理装置 5 0 , 5 1 と共有メモリ 4 2とのデータ転送の オーバ一ラップ制御、 （iii ) 処理に適した方の並列データ処理装 置をユーザが意識せずにアクセスできる機能、 （iv) システム全体 の空間的， 時間的並列処理動作をモニタ リングする機能、 を有して いる。
    [0045] これらの機能を実現するため、 システム制御ソフ トウエアでは、 様々な管理を行ない各構成要素の同時実行や排他制御を行なう。 即ち、 （i ) 二つの並列データ処理装置 5 0， 5 1の資源管理、
    [0046] ( ii) 共有メモリ 4 2の複数のセグメン 卜のデータ管理、 （iii ) 並列処理ライブラリの管理、 （iv) 並列処理ライブラリの実行制御、
    [0047] ( v ) 共有メモリ 4 2のデータ入出力管理、 を行なう。
    [0048] 次に、 本発明の画像処理への適用例について述べる。 前述のよう に画像処理には様々な処理があリ、 その処理形態の分類方法にもい くつかのものがあるが、 並列処理の観点から大別すると、 （ 1 ) 近 傍処理：画素間または近傍画素間で比較的単鈍な演算を一様に施す 処理と、 （ 2 ) 大局処理： 画像全体に対して比較的複維な演算を施 す処理、 に分かれる。
    [0049] このように性貧の異なる 2種類の処理をいずれも効率よく高速に 並列実行するために、 本発明では概ね、 近傍処理を S I M D型並列 データ処理装置 5 0、 大局処理を M I M D型並列データ処理装置 5 1 が主に分担し、 広い範囲で効率的な並列処理を可能とする。 こ のように、 両方の並列データ処理装置を使い分けることによ り、 空 間的にも時間的にも広い範囲でより適した並列処理を施すことがで きる。 また、 各処理をさらに分割してハイブリッ ド並列処理を適用 することにより、 さらに広い分野で最大限の並列処理を行なうこと が可能となる。 以下では具体的に本発明による性能面での効果につ いて述べる。
    [0050] 本発明の効果を画像処理を例に、 演算レベル， 機能レベル， 応用 プログラムレベルの各々について述べる。
    [0051] まず、 演算レベルの評価では、 一般に、 S I M D型並列デ一タ処 理装置 5 0は、 整数演算や短いビッ ト長のデータの処理に適した構 成をとることが多く、 これらの処理に対しては、 大規模な並列処理 によ り超高速性能を発揮することができる。 一方、 M I M D型並列 データ処理装置 5 1は演算器の制限から大規模な並列処理の実現は 難しいが、 浮動小数点演算や複雑な処理には適している。
    [0052] 画像処理では、 処理に応じて、 数ビッ ト整数データから 3 2ビッ ト実数データまで様々なデータを扱うが、 処理内容やデータに応じ た演算器構成を選択することによリ、 そのプロセッサの最高性能を 引き出すこ と ができる。 概ね短いビッ ト長の整数データ処理には S I M D型並列データ処理装置 5 0の方が高い性能を出すことがで き、 長いビッ ト長の実数データ処理には M I M D型並列データ処理 装置 5 1の方が高い性能を出せる。 従って、 この二つを最適に割り 当てることにより、 処理に対応した並列処理によリ最高性能を引き 出すことができる。
    [0053] 次に、 機能レベルの性能の例として、 代表的な 5つの画像処理に 対する S I M D型データ処理装置 5 0と M I M D型並列データ処理 装置 5 1 の相対性能比を示す。 図 2 に示した構成のシステムの場 合、 それぞれ、 ァフィ ン変換では 1 : 5、 ヒス トグラム作成では 1 ： 4、 濃度値変換では 2 ： 1 、 高速フーリエ変換では 3 ： 1 、 一様重み付きフィルタでは 6 ： 1であり、 性能が高い方が低い方に 比べ約 2倍から 6倍高い。 この性能評価で使用した S I M D型並列 データ処理装置 5 0と M I M D型並列データ処理装置 5 1はほぼ同 等のハードウェア量であり、 このことから、 単一の並列処理ァーキ テクチヤだけを使用するよ りも、 本発明のようにハイブリツ ドの並 列処理アーキテクチャを採る方が効率的であることがわかる。
    [0054] 最後に、 応用プログラムレベルの性能評価として、 人工衛星搭載 光学系センサ一からのデータに対する一連の実用レベルの画像処理 に対して、 本発明の評価を行なった。 その結果、 単一の並列データ 処理装置だけを使用した場合に比べ、 2 . 6倍から 2 . 8倍の性能 を得ることができ、 本発明の有効性が実証できた。 産業上の利用可能性
    [0055] 本発明によるハイブリツ ド型並列処理アーキテクチャの採用によ リ、 単一アーキテクチャに比べ時間的にも空間的にも並列処理の適 用可能範囲を大幅に広げることができ、 様々なタイブの画像処理に 対して各々の処理に適した並列処理を動的に適用することが可能と なった。 これにより、 大規模で複锥な画像データの処理のように、 従来のコンピュ一タでは有効な時間内での処理が困難だつた処理を 実用時間内で高速に処理することができる。
    权利要求:
    Claims

    請 求 の 範 囲 . 制御の流れが一つで， 処理されるデータの流れが複数である第 1の並列データ処理装置と、 制御の流れもデータの流れも複数で ある第 2の並列データ処理装置とを共有のバスとメモリで接続す るとともに、 各々の並列データ処理装置に適した処理を行わせる システム制御部を備えたことを特徴とする並列データ処理システ ム。
    . 共有バスは、 各々の並列データ処理装置が独立して使用可能な 高速多重バスからなり、 共有メモリは、 複数のセグメントに分割 され各々個別に多重バスに接続される大容量高速共有メモリから なり、 システム制御部は， ユーザプログラムが処理されるデータ 処理部と、 プログラムが格納されるメモリ部と、 処理されるデー タが格納されるディスク部と、 多重バスと接続するためのバス接 続部と、 これらを接続する内部バスとを有し、 各々の並列データ 処理装置には、 多重バスとの間でデータの入出力を行なう入出力 制御部を有し、 各々の並列データ処理装置を上記共有メモリ と高 速多重バスによ リ密結合したことを特徴とする請求の範囲第 1項 記載の並列データ処理システム。
    . 各々の並列データ処理装置をそれぞれ独立に同時に使用し、 共 有メモリ内の異なるデータに対して処理を施すハイブリッ ド並列 処理を行なうことを特徴とする請求の範囲第 1項又は第 2項記載 の並列データ処理システム。
    . 連続する一連のデータセッ 卜単位に各々の並列データ処理装置 をパイプライン的に処理させるハイプリッ ド並列処理を行なうこ とを特徴とする請求の範囲第 1項又は第 2項記載の並列データ処 理システム
    . 各々の並列データ処理装置を個別に独立に平行動作させ、 共有 メモリ内の同じデータに対して異なる並列処理を施すハイブリ ツ ド並列処理を行なう ことを特徴とする請求の範囲第 1項又は第 2 項記載の並列データ処理システム。
    . 画像処理において、 画素間または近傍画素間で比較的単鈍な演 算を一様に施す近傍処理を第 1の並列データ処理装置に、 画像全 体に対して比較的複雑な演算を施す大局処理を第 2の並列データ 処理装置に主に分担させることを特徴とする請求の範囲第 1項又 は第 2項記載の並列データ処理システム。
    类似技术:
    公开号 | 公开日 | 专利标题
    Uhr2014|Parallel computer vision
    Athanas et al.1995|Real-time image processing on a custom computing platform
    Fountain et al.1988|The CLIP7A image processor
    US5421019A|1995-05-30|Parallel data processor
    US6145072A|2000-11-07|Independently non-homogeneously dynamically reconfigurable two dimensional interprocessor communication topology for SIMD multi-processors and apparatus for implementing same
    CN107679620B|2020-05-26|人工神经网络处理装置
    USRE36954E|2000-11-14|SIMD system having logic units arranged in stages of tree structure and operation of stages controlled through respective control registers
    EP0075593B1|1989-06-21|A bit slice microprogrammable processor for signal processing applications
    US7500083B2|2009-03-03|Accelerated processing with scheduling to configured coprocessor for molecular data type by service and control coprocessor upon analysis of software code
    US5129092A|1992-07-07|Linear chain of parallel processors and method of using same
    CA1317680C|1993-05-11|Digital signal processing apparatus
    US6199093B1|2001-03-06|Processor allocating method/apparatus in multiprocessor system, and medium for storing processor allocating program
    US4789925A|1988-12-06|Vector data logical usage conflict detection
    US6126331A|2000-10-03|Determining a communication schedule between processors
    JP2770603B2|1998-07-02|並列計算機
    EP0739513B1|1999-10-27|Method of transmitting of data
    US5388236A|1995-02-07|Digital signal processor with multiway branching based on parallel evaluation of N threshold values followed by sequential evaluation of M
    US4745545A|1988-05-17|Memory reference control in a multiprocessor
    US5165023A|1992-11-17|Parallel processing system with processor array and network communications system for transmitting messages of variable length
    US7492368B1|2009-02-17|Apparatus, system, and method for coalescing parallel memory requests
    US6334177B1|2001-12-25|Method and system for supporting software partitions and dynamic reconfiguration within a non-uniform memory access system
    US5968114A|1999-10-19|Memory interface device
    US3614742A|1971-10-19|Automatic context switching in a multiprogrammed multiprocessor system
    US7051180B2|2006-05-23|Masterless building block binding to partitions using identifiers and indicators
    Aggarwal1986|Optimal bounds for finding maximum on array of processors with k global buses
    同族专利:
    公开号 | 公开日
    GB2250362A|1992-06-03|
    GB2250362B|1994-06-29|
    GB9200168D0|1992-02-26|
    US5355508A|1994-10-11|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    JPS5917657A|1982-04-26|1984-01-28|Vish Machinno Electrotech Inst|Multiplex microprocessor system|
    JPS5916071A|1982-07-19|1984-01-27|Toshiba Corp|Parallel processing system|JPWO2008126196A1|2007-03-19|2010-07-22|富士通株式会社|シミュレーション制御プログラム、記録媒体、シミュレーション装置およびシミュレーション制御方法|JPS63142445A|1986-12-05|1988-06-14|Agency Of Ind Science & Technol|Memory device|
    JPS63192153A|1987-02-05|1988-08-09|Agency Of Ind Science & Technol|Parallel data processor|
    JPS6426108A|1987-07-22|1989-01-27|Matsushita Electric Works Ltd|Thickness measuring method|
    US5239654A|1989-11-17|1993-08-24|Texas Instruments Incorporated|Dual mode SIMD/MIMD processor providing reuse of MIMD instruction memories as data memories when operating in SIMD mode|US5588152A|1990-11-13|1996-12-24|International Business Machines Corporation|Advanced parallel processor including advanced support hardware|
    US5765015A|1990-11-13|1998-06-09|International Business Machines Corporation|Slide network for an array processor|
    US5713037A|1990-11-13|1998-01-27|International Business Machines Corporation|Slide bus communication functions for SIMD/MIMD array processor|
    US5625836A|1990-11-13|1997-04-29|International Business Machines Corporation|SIMD/MIMD processing memory element |
    US5765012A|1990-11-13|1998-06-09|International Business Machines Corporation|Controller for a SIMD/MIMD array having an instruction sequencer utilizing a canned routine library|
    US5809292A|1990-11-13|1998-09-15|International Business Machines Corporation|Floating point for simid array machine|
    US5966528A|1990-11-13|1999-10-12|International Business Machines Corporation|SIMD/MIMD array processor with vector processing|
    US5594918A|1991-05-13|1997-01-14|International Business Machines Corporation|Parallel computer system providing multi-ported intelligent memory|
    EP0485690B1|1990-11-13|1999-05-26|International Business Machines Corporation|Parallel associative processor system|
    US5828894A|1990-11-13|1998-10-27|International Business Machines Corporation|Array processor having grouping of SIMD pickets|
    US5617577A|1990-11-13|1997-04-01|International Business Machines Corporation|Advanced parallel array processor I/O connection|
    US5815723A|1990-11-13|1998-09-29|International Business Machines Corporation|Picket autonomy on a SIMD machine|
    US5734921A|1990-11-13|1998-03-31|International Business Machines Corporation|Advanced parallel array processor computer package|
    US5963746A|1990-11-13|1999-10-05|International Business Machines Corporation|Fully distributed processing memory element|
    US5590345A|1990-11-13|1996-12-31|International Business Machines Corporation|Advanced parallel array processor|
    US5765011A|1990-11-13|1998-06-09|International Business Machines Corporation|Parallel processing system having a synchronous SIMD processing with processing elements emulating SIMD operation using individual instruction streams|
    US5963745A|1990-11-13|1999-10-05|International Business Machines Corporation|APAP I/O programmable router|
    US5630162A|1990-11-13|1997-05-13|International Business Machines Corporation|Array processor dotted communication network based on H-DOTs|
    US5794059A|1990-11-13|1998-08-11|International Business Machines Corporation|N-dimensional modified hypercube|
    EP0496506B1|1991-01-25|2000-09-20|Hitachi Process Computer Engineering, Inc.|Fault tolerant computer system incorporating processing units which have at least three processors|
    JPH04336378A|1991-05-14|1992-11-24|Nec Corp|Information processor|
    JP2642039B2|1992-05-22|1997-08-20|インターナショナル・ビジネス・マシーンズ・コーポレイション|アレイ・プロセッサ|
    US5872988A|1992-06-17|1999-02-16|U.S. Philips Corporation|Parallel data processing device having a concatenated data path between elementary processors|
    JP2551312B2|1992-12-28|1996-11-06|日本電気株式会社|ジョブステップ並列実行方式|
    US5420786A|1993-04-05|1995-05-30|Ims America, Ltd.|Method of estimating product distribution|
    JP3199205B2|1993-11-19|2001-08-13|株式会社日立製作所|並列演算装置|
    IL110573A|1994-08-04|1998-10-30|Orad Hi Tec Systems Ltd|Apparatus and method for video broadcasting|
    US5903771A|1996-01-16|1999-05-11|Alacron, Inc.|Scalable multi-processor architecture for SIMD and MIMD operations|
    DE19651075A1|1996-12-09|1998-06-10|Pact Inf Tech Gmbh|Einheit zur Verarbeitung von numerischen und logischen Operationen, zum Einsatz in Prozessoren , Mehrrechnersystemen, Datenflußprozessoren , digitalen Signal Prozessorenoder dergleichen|
    DE19654595A1|1996-12-20|1998-07-02|Pact Inf Tech Gmbh|I0- und Speicherbussystem für DFPs sowie Bausteinen mit zwei- oder mehrdimensionaler programmierbaren Zellstrukturen|
    US9092595B2|1997-10-08|2015-07-28|Pact Xpp Technologies Ag|Multiprocessor having associated RAM units|
    EP1329816B1|1996-12-27|2011-06-22|Richter, Thomas|Verfahren zum selbständigen dynamischen Umladen von Datenflussprozessorensowie Bausteinen mit zwei- oder mehrdimensionalen programmierbaren Zellstrukturen |
    US6542998B1|1997-02-08|2003-04-01|Pact Gmbh|Method of self-synchronization of configurable elements of a programmable module|
    DE19861088A1|1997-12-22|2000-02-10|Pact Inf Tech Gmbh|Verfahren zur Reparatur von integrierten Schaltkreisen|
    US6272616B1|1998-06-17|2001-08-07|Agere Systems Guardian Corp.|Method and apparatus for executing multiple instruction streams in a digital processor with multiple data paths|
    DE10081643D2|1999-06-10|2002-05-29|Pact Inf Tech Gmbh|Sequenz-Partitionierung auf Zellstrukturen|
    JP3922859B2|1999-12-28|2007-05-30|株式会社リコー|画像処理装置、画像処理方法およびその方法をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体|
    WO2001050240A2|1999-12-29|2001-07-12|Systemonic Ag|Anordnung und verfahren zur steuerung des datenflusses|
    US6643763B1|2000-02-28|2003-11-04|International Business Machines Corporation|Register pipe for multi-processing engine environment|
    US6766437B1|2000-02-28|2004-07-20|International Business Machines Corporation|Composite uniprocessor|
    US20010049757A1|2000-03-01|2001-12-06|Ming-Kang Liu|Programmable task scheduler for use with multiport xDSL processing system|
    US9141390B2|2001-03-05|2015-09-22|Pact Xpp Technologies Ag|Method of processing data with an array of data processors according to application ID|
    US9250908B2|2001-03-05|2016-02-02|Pact Xpp Technologies Ag|Multi-processor bus and cache interconnection system|
    US9436631B2|2001-03-05|2016-09-06|Pact Xpp Technologies Ag|Chip including memory element storing higher level memory data on a page by page basis|
    EP1342158B1|2000-06-13|2010-08-04|Richter, Thomas|Pipeline ct-protokolle und -kommunikation|
    US9552047B2|2001-03-05|2017-01-24|Pact Xpp Technologies Ag|Multiprocessor having runtime adjustable clock and clock dependent power supply|
    US9037807B2|2001-03-05|2015-05-19|Pact Xpp Technologies Ag|Processor arrangement on a chip including data processing, memory, and interface elements|
    US8686475B2|2001-09-19|2014-04-01|Pact Xpp Technologies Ag|Reconfigurable elements|
    US8058899B2|2000-10-06|2011-11-15|Martin Vorbach|Logic cell array and bus system|
    US7444531B2|2001-03-05|2008-10-28|Pact Xpp Technologies Ag|Methods and devices for treating and processing data|
    US10031733B2|2001-06-20|2018-07-24|Scientia Sol Mentis Ag|Method for processing data|
    US20030023653A1|2001-01-29|2003-01-30|Andrew Dunlop|System, method and article of manufacture for a single-cycle floating point library|
    US7844796B2|2001-03-05|2010-11-30|Martin Vorbach|Data processing device and method|
    US7996827B2|2001-08-16|2011-08-09|Martin Vorbach|Method for the translation of programs for reconfigurable architectures|
    US7434191B2|2001-09-03|2008-10-07|Pact Xpp Technologies Ag|Router|
    US8686549B2|2001-09-03|2014-04-01|Martin Vorbach|Reconfigurable elements|
    AU2003286131A1|2002-08-07|2004-03-19|Pact Xpp Technologies Ag|Method and device for processing data|
    US8914590B2|2002-08-07|2014-12-16|Pact Xpp Technologies Ag|Data processing method and device|
    US7266725B2|2001-09-03|2007-09-04|Pact Xpp Technologies Ag|Method for debugging reconfigurable architectures|
    DE10261500B4|2001-12-21|2005-07-21|Micronas Gmbh|Prozessor und Verfahren zum Steuern eines Prozessors|
    AU2003208266A1|2002-01-19|2003-07-30|Pact Xpp Technologies Ag|Reconfigurable processor|
    AT402446T|2002-02-18|2008-08-15|Pact Xpp Technologies Ag|Bussysteme und rekonfigurationsverfahren|
    US9170812B2|2002-03-21|2015-10-27|Pact Xpp Technologies Ag|Data processing system having integrated pipelined array data processor|
    US7020770B2|2002-07-12|2006-03-28|Lsi Logic Corporation|Method and apparatus for configuration of RAID controllers|
    US7657861B2|2002-08-07|2010-02-02|Pact Xpp Technologies Ag|Method and device for processing data|
    US7394284B2|2002-09-06|2008-07-01|Pact Xpp Technologies Ag|Reconfigurable sequencer structure|
    TWI227894B|2003-08-15|2005-02-11|Via Tech Inc|A method for detecting flash card|
    JP4699685B2|2003-08-21|2011-06-15|パナソニック株式会社|信号処理装置及びそれを用いた電子機器|
    EP1676208A2|2003-08-28|2006-07-05|PACT XPP Technologies AG|Data processing device and method|
    EP1735706A4|2004-03-13|2008-08-13|Cluster Resources Inc|System and method of co-allocating a reservation spanning different compute resources types|
    WO2005089240A2|2004-03-13|2005-09-29|Cluster Resources, Inc.|System and method for providing multi-resource management support in a compute environment|
    US7890629B2|2004-03-13|2011-02-15|Adaptive Computing Enterprises, Inc.|System and method of providing reservation masks within a compute environment|
    CA2559603A1|2004-03-13|2005-09-29|Cluster Resources, Inc.|System and method for providing advanced reservations in a compute environment|
    US7215808B2|2004-05-04|2007-05-08|Kla-Tencor Technologies Corporation|High throughout image for processing inspection images|
    US7996455B2|2005-06-17|2011-08-09|Adaptive Computing Enterprises, Inc.|System and method for providing dynamic roll-back reservations in time|
    US20070266388A1|2004-06-18|2007-11-15|Cluster Resources, Inc.|System and method for providing advanced reservations in a compute environment|
    US7814462B2|2004-10-29|2010-10-12|Massachusetts Institute Of Technology|Methods and apparatus for parallel execution of a process|
    DE102005048525A1|2005-10-07|2007-04-12|Micronas Gmbh|Schaltungsarchitektur für eine integrierte Schaltung|
    US7861060B1|2005-12-15|2010-12-28|Nvidia Corporation|Parallel data processing systems and methods using cooperative thread arrays and thread identifier values to determine processing behavior|
    EP1974265A1|2006-01-18|2008-10-01|PACT XPP Technologies AG|Hardwaredefinitionsverfahren|
    US8176265B2|2006-10-30|2012-05-08|Nvidia Corporation|Shared single-access memory with management of multiple parallel requests|
    US7680988B1|2006-10-30|2010-03-16|Nvidia Corporation|Single interconnect providing read and write access to a memory shared by concurrent threads|
    DE602007014413D1|2007-03-06|2011-06-16|Nec Corp|Datentransfernetzwerk und steuervorrichtung für ein system mit einem array von verarbeitungselementen, die jeweils entweder selbst- oder gemeinsam gesteuert sind|
    US7870366B2|2007-09-22|2011-01-11|Hirak Mitra|Chained operation of functional components with DONE and GO registers storing memory address for writing and reading linking signal value|
    AT535870T|2008-03-03|2011-12-15|Nec Corp|Steuervorrichtung für schnellen datenaustausch zwischen verarbeitungseinheiten in einer prozessorarchitektur mit verarbeitungseinheiten verschiedener bandbreitenverbindung mit einem pipeline-ring-bus|
    US9804995B2|2011-01-14|2017-10-31|Qualcomm Incorporated|Computational resource pipelining in general purpose graphics processing unit|
    US9092429B2|2012-10-23|2015-07-28|Analog Devices Global|DMA vector buffer|
    US9342306B2|2012-10-23|2016-05-17|Analog Devices Global|Predicate counter|
    US9201828B2|2012-10-23|2015-12-01|Analog Devices, Inc.|Memory interconnect network architecture for vector processor|
    US20160224465A1|2015-01-08|2016-08-04|Technion Research And Development Foundation Ltd.|Hybrid processor|
    US10606797B2|2018-07-05|2020-03-31|Mythic, Inc.|Systems and methods for implementing an intelligence processing computing architecture|
    法律状态:
    1991-11-14| AK| Designated states|Kind code of ref document: A1 Designated state(s): GB JP US |
    优先权:
    申请号 | 申请日 | 专利标题
    JP11726290||1990-05-07||
    JP2/117262||1990-05-07||US07/793,353| US5355508A|1990-05-07|1991-05-07|Parallel data processing system combining a SIMD unit with a MIMD unit and sharing a common bus, memory, and system controller|
    GB9200168A| GB2250362B|1990-05-07|1992-01-06|Parallel data processing system|
    [返回顶部]